package main

import (
	. "GO_data_structures_and_algorithms/tool"
)

func main() {
	var arr = []int{7, 1, 3, 5, 7, 8, 5, 1, 3, 8, 4, 9, 0}
	insertSort2(arr)
	PrintSlice(arr)
	PrintSlice(arr)
}

func insertSort1(arr []int) {

	if arr == nil || len(arr) < 2 {
		return
	}
	N := len(arr)
	for end := 1; end < N; end++ {
		newNumberIndex := end
		for newNumberIndex-1 >= 0 && arr[newNumberIndex] < arr[newNumberIndex-1] {
			//为了防止类似于零的元素一直往前换导致下标变成-1越界

			Swap(arr, newNumberIndex, newNumberIndex-1)
			newNumberIndex--

		}

	}

}
func insertSort2(arr []int) {

	if arr == nil || len(arr) < 2 {
		return
	}
	N := len(arr)
	for end := 1; end < N; end++ {

		for pre := end; pre-1 >= 0 && arr[pre-1] > arr[pre]; pre-- { //为了防止类似于零的元素一直往前换导致下标变成-1越界

			Swap(arr, pre-1, pre)

		}

	}

}
